package adelsonVelskyLandis;
/**
 * 模拟实现：高度平衡的二叉搜索树
 */
public class AVL {
    static class TreeNode {
        public TreeNode parent ;
        public TreeNode left;
        public TreeNode right;
        // 平衡因子, 右子树增加则 bf ++, 左子树增加则 bf --
        public int bf;
        public int val;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            root = node;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                return true; // 重复节点
            }
        }
        // 至此 cur 为空，parent 为 cur 的父节点
        // 完成节点的插入
        if (parent.val > val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        node.parent = parent; // 双向连接

        // parent = cur.parent;
        cur = node;
        // 开始向上搜索, 重新计算平衡因子, 平衡这棵树
        while (parent != null) {
            if (cur == parent.left) {
                parent.bf --;
            } else {
                parent.bf ++;
            }

            // 如果说 parent 的结点重新变为 0, 则说明该树平衡, 不需要再调整
            if (parent.bf == 0) {
                break;
            } else if (parent.bf == 1 || parent.bf == -1) {
                // 还算正常, 继续向上结算
                cur = parent;
                parent = cur.parent;
            } else {
                // 否则 parent 的 bf 为 2, 或者 parent 的 bf 为 -2
                if (parent.bf == -2) {
                    if (cur.bf == -1) {
                        // 左子树太高了, 需要右旋
                        rotateRight(parent);
                    } else {
                        // parent.bf == -2 && cur.bf == 1
                        // 这时候就需要 左旋 再 右旋
                        rotateLR(parent);
                    }
                } else {
                    // parent.bf == 2
                    if (cur.bf == 1) {
                        rotateLeft(parent);
                    } else { // cur.bf == -1
                        // 这时候需要先 左旋 和 右旋
                        rotateRL(parent);
                    }
                }
                // 完成了一次旋转就能够达成平衡
                break;
            }
        }
        return true;
    }

    private void rotateRL(TreeNode parent) {
        TreeNode rson = parent.right;
        TreeNode rsonLeft = rson.left;
        int bf = rsonLeft.bf;

        rotateRight(rson);
        rotateLeft(parent);


        if (bf == 1) {
            parent.bf = -1;
            rsonLeft.bf = 0;
            rson.bf = 0;
        } else if (bf == -1) { // bf = -1
            parent.bf = 0;
            rsonLeft.bf = 0;
            rson.bf = 1;
        }
    }

    private void rotateLR(TreeNode parent) {
        TreeNode lson = parent.left;
        TreeNode lsonRight  = lson.right;
        int bf = lsonRight.bf;

        rotateLeft(lson);
        rotateRight(parent);

        // 再分情况调整 平衡因子
        if (bf == 1) {
            lson.bf = -1;
            lsonRight.bf = 0;
            parent.bf = 0;
        } else if (bf == -1) { // bf == -1
            lson.bf = 0;
            lsonRight.bf = 0 ;
            parent.bf = 1;
        }
    }

    // 右子树太高, 左旋
    private void rotateLeft(TreeNode parent) {
        TreeNode rson = parent.right;
        TreeNode rsonLeft = rson.left;
        TreeNode pParent = parent.parent;

        rson.left = parent;
        parent.parent = rson;
        if (rsonLeft != null) {
            rsonLeft.parent = parent;
        }
        parent.right = rsonLeft;

        if (parent == root) {
            root = rson;
            rson.parent = null;
        } else {
            if (pParent.left == parent) {
                pParent.left = rson;
            } else {
                pParent.right = rson;
            }
            rson.parent = pParent; // 双向连接
        }
        // 再更新平衡因子
        rson.bf = parent.bf = 0;
    }

    // 右旋, 把 parent 的 左孩子提起来
    private void rotateRight(TreeNode parent) {
        // parent 的左孩子
        TreeNode lson = parent.left;
        // lson 的右孩子
        TreeNode lsonRight = lson.right;
        // parent 的父节点
        TreeNode pParent = parent.parent;


        lson.right = parent;
        parent.parent = lson;
        if (lsonRight != null) {
            lsonRight.parent = parent;
        }
        parent.left = lsonRight;

        // 再讨论根节点, 如果 parent 本来是根节点
        if (root == parent) {
            root = lson;
            lson.parent = null;
        } else {
            if (pParent.left == parent) {
                pParent.left = lson;
            } else {
                pParent.right = lson;
            }
            lson.parent = pParent;
        }
        lson.bf = parent.bf = 0;
    }

    // --------------------------

    /**
     * 测试代码
     * @param root
     */
    public void inorder(TreeNode root) {
        if(root == null) return;
        inorder(root.left);
        System.out.print(root.val+"  ");
        inorder(root.right);
    }

    private int height(TreeNode root) {
        if(root == null) return 0;
        int leftH = height(root.left);
        int rightH = height(root.right);

        return leftH > rightH ? leftH+1 : rightH+1;
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int leftH = height(root.left);
        int rightH = height(root.right);

        // 判断当前结点的 平衡因子是否正常
        if(rightH-leftH != root.bf) {
            System.out.println("这个节点："+root.val+" 平衡因子异常");
            return false;
        }

        // 判断是不是平衡树
        return Math.abs(leftH-rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

}
